package com.tsx.leetcode.hot100.easy;

import java.util.Stack;

/**
 * <a href="https://leetcode.cn/problems/valid-parentheses">有效的括号</a>
 */
public class Q20IsValidBrackets {
    public static void main(String[] args) {
        boolean valid = isValid("]");
        System.out.println(valid);
    }

    /**
     * 匹配括号
     * 核心思想：
     * 把字符串转换数组，用栈辅助。
     * 当元素是左括号时候，压栈，要是元素是右括号，就弹出
     * 看弹出的元素和当前元素是不是括号匹配 不匹配则false
     * 最后要看栈还是不是空的 因为要是全部都是左括号的话就会出现问题
     */
    public static boolean isValid(String s) {
        char[] chars = s.toCharArray();
        if (chars.length == 0) { // 如果是空字符串 肯定是匹配的直接true
            return true;
        }
        if (chars.length % 2 != 0) { // 如果是奇数串 那就直接false 因为要成对匹配
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (char c : chars) {
            if (c == '(' || c == '{' || c == '[') { // 左括号的时候压栈
                stack.push(c);
            } else {
                if (stack.isEmpty()) { // 弹出的时候要做好检查 要是本来就没有的话 证明右括号居多 所以直接false
                    return false;
                }
                char top = stack.pop(); // 弹出
                // 查看是不是匹配
                if ((c == ')' && top != '(') ||
                        (c == '}' && top != '{') ||
                        (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
